// 不同的二叉搜索树2

package Leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class solution_095 {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> result = new ArrayList<>();
        boolean[] isUsed = new boolean[n];
        TreeNode root = new TreeNode();
        BackTrace(result, isUsed, 0, root, root);
        return result;
    }

    public void BackTrace(List<TreeNode> result, boolean[] isUsed, int usedNum, TreeNode root, TreeNode currentNode) {
        if (usedNum == isUsed.length) {
            result.add(root);
        } else if (usedNum == 0) {
            for (int i = 0; i < isUsed.length; i++) {
                TreeNode newNode = new TreeNode(i + 1);

                isUsed[i] = true;
                BackTrace(result, isUsed, usedNum + 1, newNode, newNode);
                isUsed[i] = false;

            }
        } else {
            for (int i = 0; i < isUsed.length; i++) {
                if (isUsed[i] == false) {
                    TreeNode newNode = new TreeNode(i + 1);
                    isUsed[i] = true;
                    if (i + 1 > currentNode.val) {
                        currentNode.right = newNode;
                        BackTrace(result, isUsed, usedNum + 1, root, currentNode.right);
                        currentNode.right = null;
                    } else {
                        currentNode.left = newNode;
                        BackTrace(result, isUsed, usedNum + 1, root, currentNode.left);
                        currentNode.left = null;
                    }
                    isUsed[i] = false;
                }
            } // for
        } // else
    }// BackTrace
}

public class Solution095 {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new LinkedList<TreeNode>();
        }
        return recursion(1, n);
    }

    public List<TreeNode> recursion(int start, int end) {
        List<TreeNode> result = new LinkedList<>();
        // 此时无数字可当头结点
        if (start > end) {
            result.add(null);
            return result;
        }

        // 枚举头结点
        for (int i = start; i <= end; i++) {
            // 所有左子树集合
            List<TreeNode> leftTrees = recursion(start, i - 1);
            // 所有右子树集合
            List<TreeNode> rightTrees = recursion(i + 1, end);
            // 从左右子树选择一棵树与头结点拼接
            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode newTree = new TreeNode(i);
                    newTree.left = left;
                    newTree.right = right;
                    result.add(newTree);
                }
            }
        }
        return result;
    }
}
